package com.gali.leetcode.day8;

import java.util.ArrayList;
import java.util.List;

/**
 * @Auther: gali
 * @Date: 2022-07-21 19:52
 * @Description:
 */
public class Solution {
    /**
     * 链表
     */
    public class ListNode {
       int val;
       ListNode next;
       ListNode() {}
       ListNode(int val) { this.val = val; }
       ListNode(int val, ListNode next) { this.val = val; this.next = next;}
 }

    /**
     * 合并两个有序链表(递归)
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //先判断两种特殊情况
        if (list1==null){
            return list2;
        }else if(list2==null){
            return list1;
        }else if (list1.val< list2.val){
            list1.next=mergeTwoLists(list1.next,list2);
            return list1;
        }else{
            list2.next=mergeTwoLists(list1,list2.next);
            return list2;
        }
    }

    /**
     * 括号生成----回溯法
     * @param n
     * @return
     */
    List<String> list =new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        if (n<=0){
            return list;
        }
        getResult("",n,n);
        return list;
    }
    //left表示左括号的个数，right表示右括号的个数
    public void getResult(String str,int left,int right){
        if (left==0&&right==0){
            list.add(str);
            return;
        }
        if (left==right){
            //左右括号相等就添加一个左括号
            getResult(str+"(",left-1,right);
        }else{
            //左右括号不相等-----左右括号都可以加
            if (left>0){
                getResult(str+"(",left-1,right);
            }
            getResult(str+")",left,right-1);
        }
    }
}
